// https://www.lintcode.com/problem/425/

class Solution {
public:
    /**
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    void getRes(string& digits, map<char, vector<char>>& rec, string tmp, vector<string>& res, int start) {
        if (start == digits.length()) {
            res.push_back(tmp);
            return;
        }
        // for (int i = start; i < digits.size(); ++i) {
        for (char r: rec[digits[start]]) {
            tmp += r;
            getRes(digits, rec, tmp, res, start + 1);
            tmp.pop_back();
        }
        // }
    }

    vector<string> letterCombinations(string &digits) {
        map<char, vector<char>> rec;
        vector<string> res;
        if (digits.empty()) return res;
        rec['2'] = {'a', 'b', 'c'};
        rec['3'] = {'d', 'e', 'f'};
        rec['4'] = {'g', 'h', 'i'};
        rec['5'] = {'j', 'k', 'l'};
        rec['6'] = {'m', 'n', 'o'};
        rec['7'] = {'p', 'q', 'r', 's'};
        rec['8'] = {'t', 'u', 'v'};
        rec['9'] = {'w', 'x', 'y', 'z'};
        string tmp = "";
        getRes(digits, rec, tmp, res, 0);
        return res;
    }
};

// https://leetcode.cn/problems/letter-combinations-of-a-phone-number
// 常规组合模板
class Solution {
public:
    void dfs(string& digits, string& tmp, vector<string>& res, int start, map<char, string>& rec) {
        if (tmp.length() >= digits.length()) {
            res.push_back(tmp);
            return;
        }
        for (int i = start; i < digits.length(); ++i) {
            for (int j = 0; j < rec[digits[i]].size(); ++j) {
                tmp.push_back(rec[digits[i]][j]);
                dfs(digits, tmp, res, i + 1, rec);
                tmp.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        map<char, string> rec;
        vector<string> res;
        if (digits.empty()) {
            return res;
        }
        rec['1'] = "";
        rec['2'] = "abc";
        rec['3'] = "def";
        rec['4'] = "ghi";
        rec['5'] = "jkl";
        rec['6'] = "mno";
        rec['7'] = "pqrs";
        rec['8'] = "tuv";
        rec['9'] = "wxyz";
        string tmp = "";
        dfs(digits, tmp, res, 0, rec);
        return res;
    }
};

// 简化
class Solution {
public:
    map<char, string> rec;
    void getRes(string& digits, string cur, vector<string>& res, int start) {
        if (start >= digits.size()) {
            res.push_back(cur);
            return;
        }
        for (int j = 0; j < rec[digits[start]].size(); ++j) {
            cur.push_back(rec[digits[start]][j]);
            getRes(digits, cur, res, start + 1);
            cur.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty()) return res;
        rec['1'] = "";
        rec['2'] = "abc";
        rec['3'] = "def";
        rec['4'] = "ghi";
        rec['5'] = "jkl";
        rec['6'] = "mno";
        rec['7'] = "pqrs";
        rec['8'] = "tuv";
        rec['9'] = "wxyz";
        string cur = "";
        getRes(digits, cur, res, 0);
        return res;
    }
};